Berikutan kejayaan tentera Islam dalam Perang Yarmuk pada tahun 636, kerajaan Khulafa al-Rasyidin dengan pantasnya mengambil alih kawasan Syria. Baitulmaqdis telah ditawan setahun kemudian. Pada tahun 642, Mesir telah berada di bawah kekuasaan Islam. Semasa kempen penaklukan Afrika Utara, tentera Islam yang lain terus menentang Empayar Sasan Parsi dan kerajaan itu sepenuhnya ditundukkan pada tahun 650an. Bahkan, kawasan Caucasus juga telah ditakluk oleh tentera Islam dalam tempoh ini. Perluasan kuasa tentera Islam telah mengubah sempadan ketenteraan antara kerajaan Islam dan Empayar Byzantine di kawasan timur Anatolia.

Serangan ke atas kawasan Anatolia merupakan satu masalah kepada tentera Islam kerana memerlukan garis bekalan lebih panjang. Maka, Khalifah Uthman bin Affan telah menubuhkan angkatan laut yang pertama di Syria dan Mesir untuk menjaga keselamatan sepanjang perairan pantai selatan. Pada tahun 654, kepulauan Rhodes dan Cyprus jatuh ke tangan tentera laut Islam. Pada tahun yang sama, gabenor Syria iaitu Muawiyah bin Abu Sufyan telah melancarkan pencerobohan ke Anatolia. Maharaja Byzantine iaitu Constans II tahu bahawa beliau perlu mengalahkan angkatan tentera laut Islam. Perincian seterusnya tidak diketahui tetapi pada tahun 654, tentera laut Byzantine tewas dalam pertempuran Masts di pantai Anatolia. Berita bahawa khalifah Uthman telah dibunuh sampai kepada Muawiyah pada tahun 656 dan beliau kembali ke Syria. Muawiyah adalah salah seorang yang terlibat dalam perang saudara dengan Khalifah Ali bin Abi Talib. Selepas Khalifah Ali dibunuh pada tahun 661, Muawiyah menjadi khalifah seterusnya dan menubuhkan dinasti Umayyah.

Khalifah Muawiyah bercita-cita ingin menguasai kota Constantinople. Tentera Laut Islam telah melancarkan serangan dari tiga arah. Tarsus, Smyrna dan Rhodes telah ditawan oleh tentera Islam. Tentera Islam telah menjadikan ia sebagai pangkalan untuk merencanakan serangan pada masa akan datang. Pada tahun 674, tentera Arab telah menguasai Cyzicus, yang hanya terletak 100 kilometer jauhnya dari Constantinople. Peristiwa yang berlaku antara tahun 674 dan 678 diselubungi misteri dengan beberapa sumber mendakwa bahawa Constantinople telah dikepung secara berterusan oleh tentera Islam. Sementara yang lain berpendapat ia hanyalah satu siri serbuan. Tambahan lagi, tentera Byzantin telah menggunakan senjata api Yunani buat kali pertama untuk memusnahkan armada Arab. Pada tahun 678, tentera Byzantine mendarat di Syria dan mencetuskan pemberontakan yang didalangi oleh masyarakat Kristian setempat. Hal ini telah memaksa khalifah untuk menandatangani perjanjian damai dan membayar jumlah simbolik bagi membaik pulih hubungan dengan Byzantine pada tahun 679.

Sementara itu, peperangan berlaku di antara bangsa Bulgar dan Kazar di kawasan Caspia dan bangsa Bulgar terpaksa berpindah. Bangsa Bulgar yang dipimpin oleh Asparukh telah menetap di sekitar Sungai Danube antara tahun 674 dan 678. Setelah sempadan timur Byzantine telah selamat, Maharaja Constantine IV telah mewujudkan kekuatan tentera untuk berarak dan bertembung dengan ancaman baru oleh bangsa Bulgar ini. Puak Bulgar telah mengambil posisi di tempat yang bernama Ongal di Lembah Danube. Pertempuran akhirnya bermula. Selepas tiga hari bertempur, Maharaja Byzantine meninggalkan tentera kerana mungkin untuk menghadiri Persidangan Constantinople Ketiga. Apabila Asparukh melihat beberapa tentera musuh memutuskan untuk meninggalkan pertempuran itu, beliau mengambil peluang ini untuk menyerang tentera Byzantine yang ingin berundur. Tentera berkuda Bulgar menyerang mereka sepanjang laluan sehingga di Edersos, atau panggilan moden pada hari ini ialah Varna. Byzantine menanggung kerugian yang tinggi dan pada tahun berikutnya, mereka telah menandatangani perjanjian damai. Perjanjian tersebut telah menjamin sempadan Bulgaria. Malah, Maharaja Byzantine turut bersetuju untuk membayar ufti tahunan kepada puak nomad yang terus menetap di situ.

Maharaja Constantine telah digantikan oleh Justinian II pada tahun 685. Beliau sangat bercita-cita untuk menaikkan namanya. Pada tahun 687, beliau telah mengetuai satu kempen yang berjaya menentang puak Bulgar dan Slav. Selain itu, beliau telah menandantangani perjanjian baru dengan khalifah. Menurutnya, Armenia dan Cyprus kini diletakkan di bawah pemerintahan bersama. Walau bagaimanapun pada tahun 692, beliau telah menyerang umat Islam sebelum dikalahkan di Sebastopolis di Cilicia. Pada tahun 692, Maharaja Justinian telah digulingkan sekali gus menandakan permulaan tempoh yang dikenali sebagai Anarki Dua Puluh Tahun. Seramai enam raja telah memerintah ketika tempoh ini. Kerajaan Umayyah telah menggunakan masa ini untuk menguasai Afrika Utara dan Sepanyol. Seterusnya, orang-orang Arab telah mara ke Anatolia dan ternyata sekali bahawa Constantinople menjadi sasaran mereka yang berikutnya.